package sim.graphs;

import java.util.*;

public class ShortestPathsTree<T> {
	T root ;
	Set<Link<T>> edges = new HashSet<Link<T>>() ;
	Map<T, Float> costs = new HashMap<T, Float>();
	Map<T, Integer> hops = new HashMap<T, Integer>();
    Map<T, Set<T>> children = new HashMap<T, Set<T>>() ;
	
	public ShortestPathsTree( T r, kSpanner<T> spanner ) {
		root = r ;
		dijkstra( spanner ) ;
	}
	
	public float cost( T node ) {
		return costs.get( node ) ;
	}
	
	public int hops( T node ) {
		return hops.get( node ) ;
	}
	
	public double distanceTo( T node ) {
		return costs.get( node ) ;
	}
	
	public Set<T> children( T node ) {
		return children.get( node ) ;
	}
	
	public Set<Link<T>> edges() {
		return edges ;
	}
	
	private void dijkstra( kSpanner<T> spanner) {
		Map<T, T> parent = new HashMap<T, T>() ;
		LinkedList<T> nodes = new LinkedList<T>( spanner.nodes() ) ;
		
		for( T i : nodes ) {
			costs.put( i, i == root ? 0f : Float.MAX_VALUE ) ;
			hops.put( i, i == root ? 0 : Integer.MAX_VALUE ) ;
			children.put( i, new HashSet<T>() ) ;
			parent.put( i, null ) ;
		}
		
		while( ! nodes.isEmpty() ) {
			T min = null ;
			for( T i : nodes )
				min = min == null || costs.get(i) < costs.get(min) ? i : min ;
			nodes.remove( min ) ;
			
			for( Link<T> e : spanner.edges( min) ) {
				T child = e.v == min ? e.w : e.v ;
				float alt = costs.get(min) + e.cost ;
				if( alt < costs.get(child) ) {
					costs.put( child, alt) ;
					parent.put( child, min) ;
					hops.put( child, hops.get(min) + 1 ) ;
				}
			}
		}
		
		for( Map.Entry<T, T> i : parent.entrySet() ) {
			T dad = i.getValue() ; T child = i.getKey() ;
			if( dad != null ) {
				children.get( dad ).add( child ) ;
				edges.add( new Link<T>( dad, child, 0f) ) ;
			}
		}			
	}
	
}